10910. Распределение оценок

 

На экзамене один студент сдавал n предметов и получил в сумме t балов. Он сдал все n предметов, для зачета каждого следовало набрать минимум p балов. Определить, сколькими способами студент мог сдать экзамен. Например, при n = 3, t = 34, p = 10 оценки по предметам могут распределиться следующим образом:

 

 

Предмет 1

Предмет 2

Предмет 3

1

14

10

10

2

13

11

10

3

13

10

11

4

12

11

11

5

12

10

12

6

11

11

12

7

11

10

13

8

10

11

13

9

10

10

14

10

11

12

11

11

10

12

12

12

12

12

10

13

10

13

11

14

11

13

10

15

10

14

10

 

Студент может сдать экзамен 15 способами.

 

Вход. Первая строка содержит количество тестов. Каждый тест содержит в одной строке три числа n, t, p, значения каждого из которых не больше 70.

 

Выход. Для каждого теста вывести количество способов, которыми студент может сдать экзамен. Ответ является знаковым 32-битовым числом.

 

Пример входа

2

3 34 10

3 34 10

 

Пример выхода

15

15

 

 

РЕШЕНИЕ

динамическое программирование

 

Анализ алгоритма

Количество способов, которыми студент может сдать экзамен, равно количеству разложений числа t – n*p на n неотрицательных слагаемых.

Обозначим через f(n, k) количество разбиений числа n на k неотрицательных слагаемых. Если при разбиении числа n на k неотрицательных слагаемых последнее (k - ое) слагаемое равно i (0 £ i £ n), то далее число n – i следует разбить на k – 1 слагаемых, что можно совершить f(n – i, k – 1) способами. Поскольку 0 £ i £ n, то общее число разбиений f(n, k) равно f(n, k – 1) + f(n – 1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k – 1). Или то же самое что

f(n, k) =

Очевидно, что f(n, 1) = 1, так как  количество способов разбить число n на одно слагаемое равно единице (этим слагаемым будет само число n). Имеет место соотношение f(0, k) = 1, так как единственным разложением числа 0 на k слагаемых будет 0 = 0 + 0 + … + 0 (k раз). Заведем массив m, в котором положим m[k, n] = f(n, k), 1 £ k, n £ 100. Индексы массива m и функции f переставлены для удобства программирования: очередная k - ая строка массива m пересчитывается через предыдущую (k – 1) - ую строку.

 

Пример

Для n = 20 и k = 2 существует 21 разбиение: 0 + 20, 1 + 19, 2 + 18, ..., 19 + 1, 20 + 0.

Для начальных значений n, k таблица m[k, n] имеет вид:

 

k \ n

0

1

2

3

4

5

1

1

1

1

1

1

1

2

1

2

3

4

5

6

3

1

3

6

10

15

21

4

1

4

10

20

35

56

 

Реализация алгоритма

Определим размер MAX массива m и объявим сам массив m.

 

#define MAX 71

int m[MAX][MAX];

 

Обнуляем массив m. Проведем инициализацию, положив f(i, 1) = f(0, i) = 1 (0 £ i < MAX). Заметим, что

f(n, k) = f(n, k – 1) + ( f(n – 1, k – 1) + f(n – 2, k – 1) + … f(1, k – 1) + f(0, k – 1) ) =

f(n, k – 1) + f(n – 1, k)

Таким образом, значение m[i, j] можно пересчитать как сумму m[i, j – 1] и m[i – 1, j]. Находим значения всех ячеек массива m, совершая таким образом предвычисления.

 

memset(m,0,sizeof(m));

for(i = 0; i < MAX; i++) m[1][i] = m[i][0] = 1;

for(i = 2; i < MAX; i++)

  for(j = 1; j < MAX; j++)  

    m[i][j] = m[i][j-1] + m[i-1][j];

 

Читаем количество тестов tests. Для каждого теста вводим значения n, t, p. Положим t = t – n * p. Выводим результат, хранящийся в ячейке m[n, t].

 

scanf("%d",&tests);

while(tests--)

{

  scanf("%d %d %d",&n,&t,&p);

  t -= n * p;

  printf("%d\n",m[n][t]);

}